package _02_第二季._01_排序;

@SuppressWarnings("unchecked")
public class MergeSort05<E extends Comparable<E>> extends Sort<E> {
    private E[] leftArray;
    @Override
    protected void sort() {
        this.leftArray = (E[]) new Comparable[array.length>>1];
        sort(0,array.length);
    }

    /**
     * 对[begin,end)范围的元素进行归并排序
     * @param begin
     * @param end
     */
    private void sort(int begin,int end){
        if(end - begin<2) return;

        int mid = (begin+end) >> 1;

        sort(begin,mid);
        sort(mid,end);
        merge(begin,mid,end);
    }


    /**
     * 将[begin,mid)和[mid,end)两个范围内的数组进行有序合并
     * @param begin
     * @param mid
     * @param end
     */
    private void merge(int begin,int mid,int end){
        int li = 0,le = mid - begin;
        int ri = mid,re = end;
        int ai = begin;
        for(int i=li;i<le;++i){
            leftArray[i] = array[begin+i];
        }

        while(li<le){
            if(ri<re && cmp(array[ri],leftArray[li])<0){
                array[ai++] = array[ri++];
            }else{
                array[ai++] = leftArray[li++];
            }
        }
    }
}
